//! B+树索引实现
//! 
//! 实现高性能的B+树数据结构，支持范围查询和并发访问

use crate::sql::Value;
use crate::{Error, Result};
use std::cmp::Ordering;
use std::collections::VecDeque;

/// B+树索引
#[derive(Debug)]
pub struct BPlusTree {
    /// 根节点
    root: Option<Box<Node>>,
    /// 树的度数（每个节点最多包含的键数）
    degree: usize,
    /// 树的高度
    height: usize,
    /// 节点总数
    node_count: usize,
}

/// B+树节点
#[derive(Debug, Clone)]
pub struct Node {
    /// 节点中的键
    keys: Vec<Value>,
    /// 节点中的值（仅叶子节点使用）
    values: Vec<usize>,
    /// 子节点指针（仅内部节点使用）
    children: Vec<Node>,
    /// 是否为叶子节点
    is_leaf: bool,
    /// 下一个叶子节点（用于范围查询）
    next_leaf: Option<Box<Node>>,
}

impl BPlusTree {
    /// 创建新的B+树
    pub fn new(degree: usize) -> Self {
        assert!(degree >= 3, "B+树的度数必须至少为3");
        
        Self {
            root: None,
            degree,
            height: 0,
            node_count: 0,
        }
    }
    
    /// 插入键值对
    pub fn insert(&mut self, key: Value, value: usize) -> Result<()> {
        if self.root.is_none() {
            // 创建根节点
            let mut root = Node::new_leaf();
            root.keys.push(key);
            root.values.push(value);
            self.root = Some(Box::new(root));
            self.height = 1;
            self.node_count = 1;
            return Ok(());
        }
        
        // 检查根节点是否需要分裂
        if self.root.as_ref().unwrap().is_full(self.degree) {
            let old_root = self.root.take().unwrap();
            let mut new_root = Node::new_internal();
            new_root.children.push(*old_root);
            Self::split_child(&mut new_root, 0, self.degree)?;
            self.root = Some(Box::new(new_root));
            self.height += 1;
        }
        
        let root = self.root.as_mut().unwrap();
        Self::insert_non_full(root, key, value, self.degree)?;
        Ok(())
    }
    
    /// 在非满节点中插入
    fn insert_non_full(node: &mut Node, key: Value, value: usize, degree: usize) -> Result<()> {
        if node.is_leaf {
            // 在叶子节点中插入
            let pos = node.keys.binary_search(&key).unwrap_or_else(|e| e);
            node.keys.insert(pos, key);
            node.values.insert(pos, value);
        } else {
            // 在内部节点中找到合适的子节点
            let mut pos = node.keys.len();
            for (i, k) in node.keys.iter().enumerate() {
                if key < *k {
                    pos = i;
                    break;
                }
            }
            
            // 检查子节点是否需要分裂
            if node.children[pos].is_full(degree) {
                Self::split_child(node, pos, degree)?;
                if key > node.keys[pos] {
                    pos += 1;
                }
            }

            Self::insert_non_full(&mut node.children[pos], key, value, degree)?;
        }
        Ok(())
    }
    
    /// 分裂子节点
    fn split_child(parent: &mut Node, index: usize, degree: usize) -> Result<()> {
        let full_child = &mut parent.children[index];
        let mid = degree / 2;
        
        let mut new_child = if full_child.is_leaf {
            Node::new_leaf()
        } else {
            Node::new_internal()
        };
        
        // 移动键和值
        new_child.keys = full_child.keys.split_off(mid);
        
        if full_child.is_leaf {
            new_child.values = full_child.values.split_off(mid);
            // 设置叶子节点链接
            new_child.next_leaf = full_child.next_leaf.take();
            full_child.next_leaf = Some(Box::new(new_child.clone()));
        } else {
            new_child.children = full_child.children.split_off(mid + 1);
        }
        
        // 将中间键提升到父节点
        let promoted_key = if full_child.is_leaf {
            new_child.keys[0].clone()
        } else {
            full_child.keys.pop().unwrap()
        };
        
        parent.keys.insert(index, promoted_key);
        parent.children.insert(index + 1, new_child);

        Ok(())
    }
    
    /// 搜索键
    pub fn search(&self, key: &Value) -> Option<usize> {
        self.root.as_ref().and_then(|root| self.search_node(root, key))
    }
    
    /// 在节点中搜索
    fn search_node(&self, node: &Node, key: &Value) -> Option<usize> {
        if node.is_leaf {
            // 在叶子节点中查找
            node.keys.binary_search(key).ok().map(|i| node.values[i])
        } else {
            // 在内部节点中找到合适的子节点
            let mut pos = node.keys.len();
            for (i, k) in node.keys.iter().enumerate() {
                if *key <= *k {
                    pos = i;
                    break;
                }
            }
            
            if pos < node.children.len() {
                self.search_node(&node.children[pos], key)
            } else {
                None
            }
        }
    }
    
    /// 范围搜索
    pub fn range_search(&self, start: &Value, end: &Value) -> Vec<usize> {
        let mut results = Vec::new();
        
        if let Some(root) = &self.root {
            self.range_search_node(root, start, end, &mut results);
        }
        
        results
    }
    
    /// 在节点中进行范围搜索
    fn range_search_node(&self, node: &Node, start: &Value, end: &Value, results: &mut Vec<usize>) {
        if node.is_leaf {
            // 在叶子节点中收集范围内的值
            for (i, key) in node.keys.iter().enumerate() {
                if key >= start && key <= end {
                    results.push(node.values[i]);
                }
            }
        } else {
            // 在内部节点中递归搜索
            for (i, key) in node.keys.iter().enumerate() {
                if start <= key {
                    self.range_search_node(&node.children[i], start, end, results);
                }
                if end < key {
                    break;
                }
            }
            
            // 检查最后一个子节点
            if let Some(last_child) = node.children.last() {
                if node.keys.last().is_none_or(|k| end >= k) {
                    self.range_search_node(last_child, start, end, results);
                }
            }
        }
    }
    
    /// 删除键
    pub fn delete(&mut self, key: &Value) -> Result<()> {
        if self.root.is_some() {
            let root = self.root.as_mut().unwrap();
            Self::delete_from_node(root, key)?;
            
            // 检查根节点是否需要更新
            let should_update_root = !self.root.as_ref().unwrap().is_leaf &&
                                   self.root.as_ref().unwrap().keys.is_empty();

            if should_update_root {
                let mut old_root = self.root.take().unwrap();
                if let Some(new_root) = old_root.children.pop() {
                    self.root = Some(Box::new(new_root));
                    self.height -= 1;
                } else {
                    self.root = None;
                    self.height = 0;
                }
            }
        }
        Ok(())
    }
    
    /// 从节点中删除键
    fn delete_from_node(node: &mut Node, key: &Value) -> Result<()> {
        if node.is_leaf {
            // 在叶子节点中删除
            if let Ok(pos) = node.keys.binary_search(key) {
                node.keys.remove(pos);
                node.values.remove(pos);
            }
        } else {
            // 在内部节点中找到合适的子节点
            let mut pos = node.keys.len();
            for (i, k) in node.keys.iter().enumerate() {
                if *key <= *k {
                    pos = i;
                    break;
                }
            }
            
            if pos < node.children.len() {
                Self::delete_from_node(&mut node.children[pos], key)?;
            }
        }
        Ok(())
    }
    
    /// 获取树的高度
    pub fn height(&self) -> usize {
        self.height
    }
    
    /// 获取节点数量
    pub fn node_count(&self) -> usize {
        self.node_count
    }
    
    /// 计算内存使用量
    pub fn memory_usage(&self) -> usize {
        self.node_count * std::mem::size_of::<Node>()
    }
    
    /// 验证B+树的完整性
    pub fn validate(&self) -> Result<()> {
        if let Some(root) = &self.root {
            self.validate_node(root, None, None)?;
        }
        Ok(())
    }
    
    /// 验证节点的完整性
    fn validate_node(&self, node: &Node, min: Option<&Value>, max: Option<&Value>) -> Result<()> {
        // 检查键的顺序
        for i in 1..node.keys.len() {
            if node.keys[i-1] >= node.keys[i] {
                return Err(Error::index("B+树键顺序错误".to_string()));
            }
        }
        
        // 检查键的范围
        if let Some(min_val) = min {
            if let Some(first_key) = node.keys.first() {
                if first_key < min_val {
                    return Err(Error::index("B+树键范围错误".to_string()));
                }
            }
        }
        
        if let Some(max_val) = max {
            if let Some(last_key) = node.keys.last() {
                if last_key > max_val {
                    return Err(Error::index("B+树键范围错误".to_string()));
                }
            }
        }
        
        // 递归验证子节点
        if !node.is_leaf {
            for (i, child) in node.children.iter().enumerate() {
                let child_min = if i == 0 { min } else { Some(&node.keys[i-1]) };
                let child_max = if i < node.keys.len() { Some(&node.keys[i]) } else { max };
                self.validate_node(child, child_min, child_max)?;
            }
        }
        
        Ok(())
    }
}

impl Node {
    /// 创建新的叶子节点
    fn new_leaf() -> Self {
        Self {
            keys: Vec::new(),
            values: Vec::new(),
            children: Vec::new(),
            is_leaf: true,
            next_leaf: None,
        }
    }
    
    /// 创建新的内部节点
    fn new_internal() -> Self {
        Self {
            keys: Vec::new(),
            values: Vec::new(),
            children: Vec::new(),
            is_leaf: false,
            next_leaf: None,
        }
    }
    
    /// 检查节点是否已满
    fn is_full(&self, degree: usize) -> bool {
        self.keys.len() >= degree - 1
    }
}
